package com.fr.lintcode;

import java.util.Stack;

import org.junit.Test;

public class Q575 {

    /**
     * @param s: an expression includes numbers, letters and brackets
     * @return: a string
     */
    public String expressionExpand(String s) {
        // write your code here
    	Stack<String> stack = new Stack<>();
    	String tmp = null;
    	for(int i =0; i < s.length(); i++){
    		char c = s.charAt(i);
    		if(']' == c){
    			if(tmp != null){
    				stack.push(tmp);
    				tmp = null;
    			}
    			String content  = stack.pop();
    			String t = stack.pop();//[
    			while(!"[".equals(t)){
    				content = t + content;
    				t = stack.pop();
    			}
    			t = stack.pop();
    			try{
    				int j = Integer.parseInt(t);
    					String rs = "";
    					for(int k = 0; k < j; k++){
        					rs = rs + content;
        				}
    					stack.push(rs);
    			}catch(NumberFormatException e){
    				stack.push(t);
    			}
    		}else if('[' == c){
    			if(tmp != null){
    				stack.push(tmp);
    			}
    			stack.push(String.valueOf(c));
    			tmp = null;
    		}else if('0' <= c && '9' >= c){
    			if(tmp == null){
    				tmp = String.valueOf(c);
    			}else{
    				char cc = tmp.charAt(0);
    				if('0' <= cc && '9' >= cc){
    					tmp = tmp + c;
    				}else{
    					stack.push(tmp);
    					tmp = String.valueOf(c);
    				}
    			}
    		}else{
    			if(tmp == null){
    				tmp = String.valueOf(c);
    			}else{
    				char cc = tmp.charAt(0);
    				if('0' <= cc && '9' >= cc){
    					stack.push(tmp);
    					tmp = String.valueOf(c);
    				}else{
    					tmp = tmp + c;
    				}
    			}
    		}
    	}
    	if(tmp != null){
    		stack.push(tmp);
    	}
    	String rs = "";
    	while(!stack.isEmpty()){
    		rs = stack.pop() + rs;
    	}
    	return rs;
    }
    
    @Test
    public void testExpressionExpand(){
    	System.out.println(expressionExpand("3[2[ad]3[pf]]xyz"));
    }

}
